package leetcode.weekly.week305;

import java.util.Arrays;

import leetcode.helper.H;

//Solution4Test
public class Solution4ac {

	public int longestIdealString(String s, int k) {
		char[] cs = s.toCharArray();
		int[] ends = new int[26];
		Arrays.fill(ends, -1);
		int max = 0;
		for (int i = 0; i < cs.length; i++) {
			int c = cs[i] - 'a';
			ends[c] = ends[c] == -1 ? 1 : ends[c] + 1;
			max = Math.max(max, ends[c]);
			for (int j = 0; j < ends.length; j++) {
				if (c != j && ends[j] != -1) {
					if (Math.abs(j - c) <= k) {
						if (ends[c] == -1) {
							ends[c] = ends[j] + 1;
							max = Math.max(ends[c], max);
						} else if (ends[c] < ends[j] + 1) {
							ends[c] = ends[j] + 1;
							max = Math.max(ends[c], max);
						}
					}
				}
			}
		}
		return max;
	}
}
